#include "auxl.h"
#include "calc.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MILLER_RABIN_ROUNDS 5

int get_naf_weight(const big_integer *x) {
	static big_integer t, s1, s2, z;
	memcpy(&t, x, sizeof(t));
	clear_big_integer(&s1);
	s1.digits[0] = 2;
	clear_big_integer(&s2);
	int rt = 0;
	while (bi_cmp_equal(&t, 0) == 1) {
		if (t.digits[0] & 1) {
			s2.digits[0] = (t.digits[0] & 3);
			bi_minus(&z, &s1, &s2);
			bi_minus(&t, &t, &z);
			++rt;
		}
		bi_shr1(&t, &t);
	}
	return rt;
}

void exgcd(big_integer *x, big_integer *y, big_integer *d, const big_integer *a, const big_integer *b) {
	if (bi_cmp_equal(b, 0) == 0) {
		memcpy(d, a, sizeof(*a));
		clear_big_integer(x);
		x->digits[0] = 1;
		clear_big_integer(y);
		return;
	}
	big_integer *q, *r;
	q = (big_integer*)malloc(sizeof(big_integer));
	r = (big_integer*)malloc(sizeof(big_integer));
	bi_div(q, r, a, b);
	exgcd(y, x, d, b, r);
	bi_mul(q, q, x);
	bi_minus(y, y, q);
	
	free(q);
	free(r);
}

int get_inverse(big_integer *r, const big_integer *a, const big_integer *m) {
	static big_integer x, y, d;
	exgcd(&x, &y, &d, a, m);
	if (bi_cmp_equal(&d, 1) != 0) {
		return 1;
	}
	bi_plus(&x, &x, m);
	bi_div(NULL, r, &x, m);
	return 0;
}

void get_random_odd(big_integer *r, int b) {
	clear_big_integer(r);
	set_bit(r, b - 1);
	set_bit(r, 0);
	for (int i = b - 2; i > 0; --i) {
		if (rand() & 1) {
			set_bit(r, i);
		}
	}
}

int miller_rabin(const big_integer *x) {
	static big_integer a, r, u, t;
	clear_big_integer(&u);
	u.digits[0] = 1;
	bi_minus(&u, x, &u);

	clear_big_integer(&a);
	for (int round = 0; round < MILLER_RABIN_ROUNDS; ++round) {
		a.digits[0] = (rand() & (((uint64_t)1 << 32) - 1));

		bi_mpow(&r, &a, &u, x);
		if (bi_cmp_equal(&r, 1) != 0) {
			return 1;
		}

		while ((u.digits[0] & 1) == 0) {
			bi_shr1(&u, &u);
			bi_mpow(&r, &a, &u, x);
			if (bi_cmp_equal(&u, 1) == 0) {
				continue;
			}
			bi_minus(&t, x, &r);
			if (bi_cmp_equal(&t, 1) != 0) {
				return 1;
			}
		}
	}

	return 0;
}

int get_random_prime(big_integer *r, int b) {
	if (b < 2 || b > K_BITS) {
		return 1;
	}
	int cnt = 0;
	do {
		get_random_odd(r, b);
		if (++cnt % 100 == 0) {
			printf("%dth time\n", cnt);
			print_big_integer(r);
		}
	} while (miller_rabin(r) != 0);
	return 0;
}
